#include<stdio.h>
#include<stdlib.h>
#define bool int
#define false 0
#define true 1
//判断回文结构,利用查找的方法找到中间的元素，断开，将后半段反转进行比较。
typedef struct SListNode
{
	int data;
	struct SListNode* next;
}SListNode;
struct SListNode* reverseList(SListNode* head)
{
    SListNode* newNode = NULL;
    SListNode* cru = head;

    while (cru)
    {
        SListNode* NEXT = cru->next;
        cru->next = newNode;
        newNode = cru;
        cru = NEXT;
    }
    return newNode;
}

bool isPalindromeList(SListNode* head)
{
	if (head == NULL)
	{
		return true;
	}
	SListNode* fast = head;
	SListNode* slow = head;
	SListNode* prev = NULL;
	while (fast && fast->next)//查找中间元素
	{
		prev = slow;
		slow = slow->next;
		fast = fast->next->next;
	}
	//断链表
	prev->next = NULL;
	//反转链表
	slow = reverseList(slow);
	//对比链表
	SListNode* cur1 = head;
	SListNode* cur2 = slow;
	while (cur1)
	{
		if (cur1->data != cur2->data)
		{
			return false;
		}
		else
		{
			cur1 = cur1->next;
			cur2 = cur2->next;
		}
	}
	return true;
}
int main()
{
	SListNode* n1 = (SListNode*)malloc(sizeof(SListNode));//创建5个节点，为了测试分割链表函数
	SListNode* n2 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n3 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n4 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n5 = (SListNode*)malloc(sizeof(SListNode));
	SListNode* n6 = (SListNode*)malloc(sizeof(SListNode));

	SListNode* plist = n1;//指向头节点的头指针plist
	n1->data = 1;//给每个节点都赋值
	n2->data = 2;
	n3->data = 3;
	n4->data = 3;
	n5->data = 2;
	n6->data = 1;

	n1->next = n2;//手动构建链表
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = NULL;

	int a=isPalindromeList(plist);
	printf("%d", a);
	return 0;

}